package com.lql.seek;

import java.util.ArrayList;

/**
 * 插值查找（改进后的二分查找）
 */
public class InsertSeek {
    private static int count = 0;

    public static void main(String[] args) {
        int[] arrays = {1, 2, 3, 4, 5, 6, 6};
        System.out.println(insertSeek(arrays, 6, 0, arrays.length - 1));
        System.out.println("查询次数：" + count);
    }

    /**
     * 插值查找实现 查找到所有匹配的值，放入集合中
     *
     * @param arr   待查找的数组
     * @param val   目标值
     * @param left  左侧下标索引
     * @param right 右侧下标索引
     * @return 返回匹配的索引集合
     */
    public static ArrayList<Integer> insertSeek(int[] arr, int val, int left, int right) {
        count++;
        if (left > right || val < arr[0] || val > arr[arr.length - 1]) {
            //未找到
            return null;
        }
        int middle = left + (right - left) * (val - arr[left]) / (arr[right] - arr[left]);
        int middleValue = arr[middle];
        if (middleValue > val) {
            //向左递归
            return insertSeek(arr, val, left, middle - 1);
        } else if (middleValue < val) {
            //向右递归
            return insertSeek(arr, val, middle + 1, right);
        } else {
            //中间值为要查找的值
            ArrayList<Integer> seekIntegers = new ArrayList<>();
            int index = middle - 1;
            while (index > 0 && arr[index] == val) {
                //向左扫描
                seekIntegers.add(index);
                index--;
            }
            seekIntegers.add(middle);
            index = middle + 1;
            while (index < arr.length && arr[index] == val) {
                //向右扫描
                seekIntegers.add(index);
                index++;
            }
            return seekIntegers;
        }
    }
}
